package com.sicheng.蓝桥.国赛准备.第10届CPP;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/28 14:23
 */
public class B质数拆分 {
    /**
     * B-质数拆分：
     * 把2019分成若干个素数相加，求有多少种分法。
     * <p>
     * 元素完全相同的算同一种方法，比如 2+2017=2019和2017+2=2019
     * <p>
     * 思路：先预处理出 2~2019中所有的素数，然后写01背包即可
     */
    public static void main(String[] args) {
        long s = System.currentTimeMillis();
        int count = 0;
        int n = 2020;
        boolean[] notPrime = new boolean[n];
        int[] prime = new int[n];
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                prime[count++] = i;
            }

            for (int j = 0; j < count && i * prime[j] < n; j++) {
                notPrime[i * prime[j]] = true;
                if (i % prime[j] == 0)
                    break;
            }

        }

        long[] dp = new long[n];
        dp[0] = 1;

        for (int i = 0; i < count; i++) {
            for (int j = n - 1; j >= prime[i]; j--) {
                dp[j] += dp[j - prime[i]];
            }
        }
        System.out.println(dp[n - 1]);
        long end = System.currentTimeMillis();
        System.out.println("总耗时: {} ms".replace("{}", end - s + ""));
    }
}
